<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns="http://www.w3.org/TR/REC-html40"><head>
<title>Problem C - Generating Fast Sorted Permutation</title>
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type">
<meta content="Word.Document" name="ProgId">
<meta content="MSHTML 5.00.2920.0" name="GENERATOR">
<meta content="Microsoft Word 9" name="Originator"><link href="http://online-judge.uva.es/p/v100/p9_files/filelist.xml" rel="File-List"><!--[if gte mso 9]><xml>
 <o:DocumentProperties>
  <o:Author>RAC</o:Author>
  <o:LastAuthor>Administrator</o:LastAuthor>
  <o:Revision>32</o:Revision>
  <o:TotalTime>522</o:TotalTime>
  <o:LastPrinted>1999-05-07T21:27:00Z</o:LastPrinted>
  <o:Created>2001-02-12T07:55:00Z</o:Created>
  <o:LastSaved>2001-02-17T15:45:00Z</o:LastSaved>
  <o:Pages>1</o:Pages>
  <o:Words>211</o:Words>
  <o:Characters>1203</o:Characters>
  <o:Company>CSE, BUET</o:Company>
  <o:Lines>10</o:Lines>
  <o:Paragraphs>2</o:Paragraphs>
  <o:CharactersWithSpaces>1477</o:CharactersWithSpaces>
  <o:Version>9.2720</o:Version>
 </o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:WordDocument>
  <w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
  <w:DisplayVerticalDrawingGridEvery>0</w:DisplayVerticalDrawingGridEvery>
  <w:UseMarginsForDrawingGridOrigin/>
  <w:Compatibility>
   <w:FootnoteLayoutLikeWW8/>
   <w:ShapeLayoutLikeWW8/>
   <w:AlignTablesRowByRow/>
   <w:ForgetLastTabAlignment/>
   <w:LayoutRawTableWidth/>
   <w:LayoutTableRowsApart/>
  </w:Compatibility>
 </w:WordDocument>
</xml><![endif]-->
<style>P.MsoNormal {
	COLOR: black; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; mso-bidi-font-size: 10.0pt; mso-style-parent: ""; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
LI.MsoNormal {
	COLOR: black; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; mso-bidi-font-size: 10.0pt; mso-style-parent: ""; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
DIV.MsoNormal {
	COLOR: black; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; mso-bidi-font-size: 10.0pt; mso-style-parent: ""; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
P.MsoBodyText {
	COLOR: black; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; TEXT-ALIGN: justify; mso-bidi-font-weight: bold; mso-bidi-font-size: 10.0pt; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
LI.MsoBodyText {
	COLOR: black; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; TEXT-ALIGN: justify; mso-bidi-font-weight: bold; mso-bidi-font-size: 10.0pt; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
DIV.MsoBodyText {
	COLOR: black; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; TEXT-ALIGN: justify; mso-bidi-font-weight: bold; mso-bidi-font-size: 10.0pt; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
EM {
	mso-bidi-font-style: normal
}
P.Preformatted {
	FONT-FAMILY: "Courier New"; FONT-SIZE: 10pt; LAYOUT-GRID-MODE: char; MARGIN: 0in 0in 0pt; mso-pagination: none; mso-fareast-font-family: "Times New Roman"; mso-style-name: Preformatted; tab-stops: 0in 47.95pt 95.9pt 143.85pt 191.8pt 239.75pt 287.7pt 335.65pt 383.6pt 431.55pt 479.5pt; mso-bidi-font-family: "Times New Roman"
}
LI.Preformatted {
	FONT-FAMILY: "Courier New"; FONT-SIZE: 10pt; LAYOUT-GRID-MODE: char; MARGIN: 0in 0in 0pt; mso-pagination: none; mso-fareast-font-family: "Times New Roman"; mso-style-name: Preformatted; tab-stops: 0in 47.95pt 95.9pt 143.85pt 191.8pt 239.75pt 287.7pt 335.65pt 383.6pt 431.55pt 479.5pt; mso-bidi-font-family: "Times New Roman"
}
DIV.Preformatted {
	FONT-FAMILY: "Courier New"; FONT-SIZE: 10pt; LAYOUT-GRID-MODE: char; MARGIN: 0in 0in 0pt; mso-pagination: none; mso-fareast-font-family: "Times New Roman"; mso-style-name: Preformatted; tab-stops: 0in 47.95pt 95.9pt 143.85pt 191.8pt 239.75pt 287.7pt 335.65pt 383.6pt 431.55pt 479.5pt; mso-bidi-font-family: "Times New Roman"
}
DIV.Section1 {
	page: Section1
}
</style>
</head><body style="" bgcolor="#ffffff" lang="EN-US">
<div class="Section1">
<p class="MsoNormal" style="text-align: center;" align="center"><b>
<font face="Times New Roman" size="5">Problem C</font></b><b style=""> <br></b><b style=""><font face="Times New Roman" size="6"><b>Generating Fast, Sorted Permutation</b></font><b></b></b></p>
<p class="MsoNormal" style="text-align: center;" align="center">
<b style=""><b style="">Input:</b><span style=""> Standard Input<o:p></o:p></span></b></p>
<p class="MsoNormal" style="text-align: center;" align="center"><b style=""><b style="">Output: </b><span style="">Standard Output<o:p></o:p></span></b></p><b style=""></b>
<p class="MsoNormal"><span style="color: windowtext;">
<!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></p>
<p class="MsoNormal"><span style="color: windowtext;">Generating permutation has 
always been an important problem in computer science. In this problem you will 
have to generate the permutation of a given string in ascending order. <span style="">&nbsp;</span>Remember that your algorithm must be 
efficient.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color: windowtext;"><br></span><b>
<font face="Times New Roman" size="5">Input</font></b>
<span style="color: windowtext;"> <o:p></o:p></span></p>
<p class="MsoNormal"><span style="color: windowtext;">The first line of the 
input contains an integer n, which indicates how many strings to follow. The 
next n lines contain n strings. Strings will only contain alpha numerals and 
never contain any space. The maximum length of the string is 
10.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color: windowtext;"><span style="">&nbsp;</span><br></span><b>
<font face="Times New Roman" size="5">Output</font></b><span style="color: windowtext;"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="color: windowtext;">For each input string 
print all the permutations possible in ascending order. Not that the strings 
should be treated, as case sensitive strings and no permutation should be 
repeated. A blank line should follow each output set.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color: windowtext;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></p>
<p class="MsoNormal" style="text-align: justify;">
<b style=""><font size="5">Sample Input</font></b></p>
<font face="Courier" size="3">
3<br>
ab<br>
abc<br>
bca<br><p></p>
</font>
<p class="MsoNormal" style="text-align: justify;"><span style="color: windowtext;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></p>
<p class="MsoNormal" style="text-align: justify;"><b style=""><font face="Times New Roman" size="5">Sample 
Output</font></b></p>
<font face="Courier">
ab<br>
ba<br>
<br>
abc<br>
acb<br>
bac<br>
bca<br>
cab<br>
cba<br>
<br>
abc<br>
acb<br>
bac<br>
bca<br>
cab<br>
cba<br>
<br>
</font>
<hr>
Shahriar Manzoor
</div></body></html>